package com.sheng.leetcode.year2023.month05.day04;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/05/04
 * <p>
 * 2106. 摘水果<p>
 * <p>
 * 在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，<p>
 * 其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。<p>
 * fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。<p>
 * 另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。<p>
 * 在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。<p>
 * 你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。<p>
 * 返回你可以摘到水果的 最大总数 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4<p>
 * 输出：9<p>
 * 解释：<p>
 * 最佳路线为：<p>
 * - 向右移动到位置 6 ，摘到 3 个水果<p>
 * - 向右移动到位置 8 ，摘到 6 个水果<p>
 * 移动 3 步，共摘到 3 + 6 = 9 个水果<p>
 * <p>
 * 示例 2：<p>
 * 输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4<p>
 * 输出：14<p>
 * 解释：<p>
 * 可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。<p>
 * 最佳路线为：<p>
 * - 在初始位置 5 ，摘到 7 个水果<p>
 * - 向左移动到位置 4 ，摘到 1 个水果<p>
 * - 向右移动到位置 6 ，摘到 2 个水果<p>
 * - 向右移动到位置 7 ，摘到 4 个水果<p>
 * 移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果<p>
 * <p>
 * 示例 3：<p>
 * 输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2<p>
 * 输出：0<p>
 * 解释：<p>
 * 最多可以移动 k = 2 步，无法到达任一有水果的地方<p>
 * <p>
 * 提示：<p>
 * 1 <= fruits.length <= 10^5<p>
 * fruits[i].length == 2<p>
 * 0 <= startPos, positioni <= 2 * 10^5<p>
 * 对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）<p>
 * 1 <= amounti <= 10^4<p>
 * 0 <= k <= 2 * 10^5<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps">2106. 摘水果</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2106 {

    @Test
    public void test01() {
        int[][] fruits = {};
        int startPos = 0, k = 0;
        System.out.println(new Solution().maxTotalFruits(fruits, startPos, k));
    }
}

/**
 * 我们不妨假设移动的位置区间为 [l, r]，开始位置为 startPos ，来看看如何算出移动的最小步数。根据 startPos 所处的位置，我们可以分为三种情况：
 * 如果 startPos ≤ l，那么就是从 startPos 向右移动到r。移动的最小步数为 r − startPos；
 * 如果 startPos ≥ r，那么就是从 startPos 向左移动到l。移动的最小步数为 startPos − l；
 * 如果 l < startPos < r，那么可以从startPos 向左移动到 l，再向右移动到 r；
 * 也可以从 startPos 向右移动到 r，再向左移动到 l。移动的最小步数为 r − l + min(∣startPos − l∣, ∣r − startPos∣)。
 * 以上三种情况可以统一用式子 r − l + min(∣startPos − l∣, ∣r − startPos∣) 表示。
 * 假设我们固定区间右端点 r，向右移动左端点 l，我们来看看最小移动步数是怎么变化的。
 * 如果 startPos ≤ l，随着 l 的增大，最小步数不会发生变化。
 * 如果 startPos > l，随着 l 的增大，最小步数会减小。
 * 因此，随着 l 的增大，最小移动步数一定是非严格单调递减的。
 * 基于此，我们可以使用双指针的方法，找出所有符合条件的最大区间，然后取所有符合条件的区间中水果总数最大的一个作为答案。
 * 具体地，我们用两个指针 i 和 j 分别指向区间的左右下标，
 * 初始时 i = j = 0。另外用一个变量 s 记录区间内的水果总数，初始时 s = 0。
 * 每次我们将 j 加入区间中，然后更新 s = s + fruits[j][1]。
 * 如果此时区间内的最小步数 fruits[j][0] − fruits[i][0] + min(∣startPos − fruits[i][0]∣, ∣startPos − fruits[j][0]∣) 大于 k，
 * 那么我们就将 i 循环向右移动，直到 i > j 或者区间内的最小步数小于等于 k。此时我们更新答案 ans = max(ans, s)。
 * 继续移动 j，直到 j 到达数组末尾。
 * 最后返回答案即可。
 */
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int ans = 0, s = 0;
        for (int i = 0, j = 0; j < fruits.length; ++j) {
            int pj = fruits[j][0], fj = fruits[j][1];
            s += fj;
            while (i <= j && pj - fruits[i][0] + Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - pj)) > k) {
                s -= fruits[i++][1];
            }
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

//作者：lcbin
//链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solution/python3javacgotypescript-yi-ti-yi-jie-sh-59o2/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
